# -*- coding:utf-8 -*-
class Solution:
    def hasPath(self, matrix, rows, cols, path):
        # write code here
        if matrix == None or rows < 1 or cols < 1 or path == None:
            return False
        a = [False] * len(matrix)
        pathlength = 0
        for i in range(rows):
            for j in range(cols):
                if self.find(matrix, rows, cols, path, i, j, pathlength, a):
                    return True
        return False

    def find(self, matrix, rows, cols, path, row, col, pathlength, a):
        if len(path) == pathlength:
            return True
        curpath = False
        if matrix[row * cols + row] == path[pathlength] and 0 <= row < rows and 0 <= col < cols and a[row * cols + row] == False:
            a[row * cols + row] = True
            pathlength += 1
            curpath = self.find(matrix, rows, cols, path, row + 1, col, pathlength, a) or self.find(matrix, rows, cols,
                                                                                                    path, row - 1, col,
                                                                                                    pathlength,
                                                                                                    a) or self.find(
                matrix, rows, cols, path, row, col + 1, pathlength, a) or self.find(matrix, rows, cols, path, row,
                                                                                    col - 1, pathlength, a)

            if not curpath:
                pathlength -= 1
                a[row * cols + row] = False
        return curpath

s = Solution()
ifTrue = s.hasPath("ABCESFCSADEE", 3, 4, "ABCCED")
ifTrue2 = s.hasPath("ABCEHJIGSFCSLOPQADEEMNOEADIDEJFMVCEIFGGS", 5, 8, "SGGFIECVAASABCEHJIGQEM")
print(ifTrue2)